package com.coder.algorithm.leetcode

/**
 * [28. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)
 *
 * @author yuhus
 * @date: 2022/3/28
 */
class l_0028 {
    /**
     * KMP（Knuth-Morris-Pratt） 算法
     */
    fun strStr(haystack: String, needle: String): Int {
        if (needle.isEmpty()) {
            return 0
        }
        val next = getNext(needle)
        var i = 0
        var j = 0
        //1. 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        while (i < haystack.length && j < needle.length) {
            if (j == -1 || haystack[i] == needle[j]) {
                i++
                j++
            } else {
                //2. 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                // next[j]即为j所对应的next值
                j = next[j]
            }
        }
        if (j == needle.length) {
            return i - j
        }
        return -1
    }

    private fun getNext(p: String): IntArray {
        val next = IntArray(p.length)
        next[0] = -1
        var k = -1
        var j = 0
        while (j < p.length - 1) {
            // p[k]表示前缀，p[j] 表示后缀
            if (k == -1 || p[k] == p[j]) {
                k++
                j++
                next[j] = k
            } else {
                k = next[k]
            }
        }
        return next
    }

    /**
     * 暴力破解
     */
    fun strStr_solution1(haystack: String, needle: String): Int {
        if (needle.isEmpty()) {
            return 0
        }
        for (i in 0 until haystack.length - needle.length + 1) {
            for (j in needle.indices) {
                if (haystack[i + j] != needle[j]) {
                    break
                } else if (j == needle.length - 1) {// 匹配
                    return i
                }
            }
        }
        return -1
    }

    /**
     * 暴力破解代码改进
     */
    fun strStr_solution2(haystack: String, needle: String): Int {
        var i = 0
        var j = 0
        while (i < haystack.length && j < needle.length) {
            if (haystack[i] == needle[j]) {
                i++
                j++
            } else {
                i = i - j + 1
                j = 0
            }
        }
        if (j == needle.length) {
            return i - j
        }
        return -1
    }
}